1. Field of the Invention
The invention relates generally to the field of electronic design automation (EDA), and particularly to a system and method for generically inferring sequential logic elements to generate a netlist for the desired circuit.
2. Description of the Related Field
EDA generally refers to a powerful process that allows designers to describe a desired digital circuit on an abstract, functional level, the Register Transfer Level (RTL) using Hardware Description Language (HDL). The functionality of the design can then be verified mathematically through circuit simulation. Logic synthesis automatically converts the RTL description to a gate-level netlist. Subsequent steps parse the netlist to place the gates on the chip floor. Finally, a routing process determines the physical layout necessary to create the requisite connections between the gates. From the physical layout, the silicon for the resulting integrated circuit can be fabricated.
The logic synthesis step requires both the RTL expression of the desired circuit as well as a library of predefined sequential cells, or blocks of logic functionality. A sequential inferrer assembles sequential cells into a netlist of interconnected cells that have the functionality of the RTL description. Specifically, a sequential cell server provides the process with the specific cells necessary to achieve the desired functionality. The server either obtains the requested cell directly from the library or, more significantly, it generates the requested cell by combining one or more functions from the basic cells in the library. When an inferred cell is necessary, the cell server compares the component parts of the requested cell against the library of available cells. The cells can be broken down into output portions, input portions, clock portions, and asynchronous portions. Candidate cells are selected from the library that match the output, clock and asynchronous portions of the requested cell. Then, the server determines whether each candidate cell's input function can be transformed via inhibition, transformation or combinational inference to match that of the requested cell. When an appropriate candidate is selected, the cell can be transformed and incorporated into the netlist. Typically, more than one candidate cell can be transformed to achieve the desired functionality. Therefore, the successful candidate cells can be further screened to optimize other necessary criteria such as size, power consumption, signal integrity, routing constraints and the like.
An example of prior art logic synthesis involves the use of full rule-based transformation. As discussed above, the transformation process focuses on the data input portion of a sequential cell. Data input functions lie between the data input terminals and the clock mediated flipflop or latch. Thus, for the purposes of this invention, data input functions are always synchronous and the functions comprise the set of combinational elements that operate on the data input. These elements can either be simply a wire or a gate, including an AND gate (for a reset function), an OR gate (for a set function), a multiplexer (“MUX”—for selecting), or an inverter (to toggle). The elements are assigned a position based on their relation between the data input and the flipflop such that the closest element to the flipflop is the first position.
The nature of the elements allows some reduction in the possibility of combinations. For example, the Toggle and MUX elements have forbidden positions (they must be set in the last position of the function), and the Toggle and MUX elements are mutually exclusive (they cannot be present in the same function). It is possible to simplify the process somewhat by constraining the number of elements that may be used. For example, allowing each element to be inferred only once results in 258 possible combinations without either a MUX or Toggle element, 258 combinations with a Toggle element and 170 combinations with a MUX element, for a total of 686 different functions. Accommodating each of these possible combinations with a full rule-based mechanism requires a total of 470,596 transformation rules (686 possible requested cells multiplied by 686 possible candidate cells). Allowing the elements to appear more than once exacerbates the problem. For example, allowing up to five positions results in more than 3000 functions and correspondingly requires more than one million rules. As exemplified below, this available system can accommodate simple transformations, but more complex functions illustrate the limitations of the system.
In a first example, the requested cell has a data input function of Reset active high. To apply the full rule-based system, each candidate is screened to determine if it has a Reset element. If so, then the inferrer must confirm the polarity on the synchronous reset terminal and inhibit (replace with a simple connection) any other elements, such as Scan, ScanMux or Set. If the candidate does not contain a Reset element, then a Scan element can be set to a constant to transform it, the MUX and Set elements can be inhibited, or if no Scan is present a synchronous Reset can be inferred. Since only a few rules are necessary for this example, the rule based transformation can be adequate for relatively simple functions such as Set, Reset or Scan.
A requested cell having an active high synchronous Set Reset function presents a more complicated example. For a simple flipflop candidate cell, the full rule based system requires the addition of appropriate AND and OR gates. If the candidate is an active low Scan flipflop, the active low Scan must be transformed into a Reset and an OR gate must be added. On the other hand, if the candidate is an active high ScanMux flipflop, the active high Scan is transformed into a Reset and the MUX is transformed into Set. Finally, if the candidate is an active high Reset high recirculating flipflop, the Reset is kept, the recirculating element is inhibited and an OR gate is added. This example demonstrates that a specific rule is required for each type of candidate cell depending on parameters such as whether a Scan or ScanMux is available. Accordingly, the number of possible combinations discussed above indicates that the full rule-based system is essentially unmanageable for more sophisticated data input functions such as the Scan Set Reset function.
Another prior art sequential inferrer utilizes a Boolean matching system. In S. Krishnamoorthy, F. Maihlot “Boolean matching of sequential elements”, 31st Design Automation Conference, 1994, the sequential cells are analogized to boolean expressions allowing the requested cell to be screened against the library. This teaching is hereby incorporated in its entirety by reference thereto for its disclosure of sequential inference and logic synthesis. However, this system works only if the requested cell finds an exact match in the library. It does not provide a means for transforming the basic cells of the library into requested cells that do not match. Further, the system does not maximize the number of candidates since only matches are identified, not candidates that could be transformed into matches. As discussed above, it is important to identify as many candidates as possible to permit optimization of other criteria.
Thus, there is a need for a sequential inferrer having a cell server capable of efficiently identifying candidate cells that may be transformed into a requested cell. There is also a need for an inferrer capable of transforming sophisticated logic functions and cells comprising multiple elements. Similarly, there is a need for an inferrer that maximizes the number of suitable candidate cells from a given library. Additionally, there is a need for a sequential inferrer that permits accurate cost estimation of the resulting circuit. There is also a need for an inferrer that uses a minimum number of rules to accommodate the various transformations necessary to convert a candidate cell into a requested cell. This invention satisfies these and other needs.